#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
using namespace std;

//860.柠檬水找零问题
bool lemonadeChange(vector<int>& bills){
    //设置两个变量一个用来表示5元的个数，一用来表示10元的个数
    int five = 0, ten = 0;

    for(auto x : bills){
        //如果给的是5元，直接收下
        if(x==5){
            five++;
        }
        //如果给的是10元，先判度是否有5元找零，有就找零收下，没有就返回
        if(x==10){
            if(five==0){
                return false;
            }
            else{
                five--;
                ten++;
            }
        }
        //如果给的是20元，有三种情况
        if(x==20){
            //贪心思想，优先考虑10+5找零
            if(ten&&five){
                five--;
                ten--;
            }
            //第一种不能找零，再考虑第二种找零方式5+5+5
            else if(five>=3){
                five -= 3;
            }
            //如果两种情况都不能找零，返回
            else{
                return false;
            }
        }
    }
    return true;
}

//2208.将数组和减半的最小操作数
int halveArray(vector<int>& nums){
    //建立一个大根堆
    priority_queue<double> heap;

    //遍历数组求和并存放到堆中
    double sum = 0.0;
    for(int x : nums){
        heap.push(x);
        sum += x;
    }

    //先获取数组和的一半，每次减去堆顶元素的一半直到减为小于等于0
    sum /= 2.0;
    int count=0;
    while(sum>0){
        //获取堆顶元素的一半,并删去
        double t = heap.top() / 2.0;
        heap.pop();
        count++;
        sum -= t;
        heap.push(t);
    }

    return count;
}

//179.最大数
string largestNumber(vector<int>& nums){
    //先将每个数字转换成字符串，存放到字典数组中
    vector<string> dictionary;
    for(auto x : nums){
        dictionary.push_back(to_string(x));
    }

    //使用Lambda表达式自定义排序规则
    sort(dictionary.begin(), dictionary.end(), [&](const string& s1, const string& s2){
        return s1 + s2 > s2 + s1; 
    });

    string ret;
    for(auto s : dictionary){
        ret += s;
    }

    if(ret[0]=='0'){
        return "0";
    }
    return ret;
}

//376.摆动序列
//全局变量表示左侧的峰值
int left = 0;
int wiggleMaxLength(vector<int>& nums){
    //寻找波峰和波谷
    int ret = 0;

    for (int i = 0; i < nums.size(); i++){
        //如果是最后一个位置，直接+1
        if(i==nums.size()-1){
            ret++;
            break;
        }
        //先计算当前位置右侧的峰值
        int right = nums[i + 1] - nums[i];
        //如果右侧峰值等于0，跳过
        if(right==0){
            continue;
        }

        //如果左右两侧峰值相乘小于0，表示当前位置是波峰或者波谷
        if(left*right<=0){
            ret++;
        }

        //将当前位置的右侧峰值赋值给左侧，表示下一个位置的左侧峰值
        left = right;
    }

    return ret;
}

int main(){

    return 0;
}